package 子数组问题;

/**
 * @Date 2024/6/10 22:35
 * @description: 力扣152: 乘积最大子数组
 * .            https://leetcode.cn/problems/maximum-product-subarray/description/
 * @Author LittleNight
 */
public class likou152 {

    // 和最大子数组和很类似, 但是还有点不太一样

    // 也可以不添加虚拟节点, 此处加了为了习惯加虚拟节点
    // 时间:O(N) 空间:O(2N)
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1]; //表示以i位置为结尾的所有子数组的乘积最大和
        int[] g = new int[n + 1]; //以i位置为结尾的所有子数组的乘积乘积最小和 (找出最小值,乘以负数,有可能是最大) (详解看视频)
        f[0] = 1;
        g[0] = 1; // 注意这个题比之前的最大子数组和不同, 那次我们没有添加虚拟节点, 此处我们新加了一个格子, 所以要进行初始化确保后面的值是对的

        int ret = -0x3f3f3f3f;
        // 注意这里是多加了一个数组格子, 所以要注意和nums[i]的下标映射
        for (int i = 1; i < n + 1; i++) {
            int x = nums[i - 1];
            f[i] = Math.max(x, Math.max(f[i - 1] * x, g[i - 1] * x));
            g[i] = Math.min(x, Math.min(f[i - 1] * x, g[i - 1] * x));

            // 边遍历边更新, dp[0] 是虚拟节点, 不是我们要的答案
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }
}
